package com.lun.medium;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import com.lun.util.BinaryTree.TreeNode;

public class FindDuplicateSubtrees {
	
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
    	List<TreeNode> result = new ArrayList<>();
    	Map<String, Integer> cache = new HashMap<>();
    	findDuplicateSubtrees(root, cache, result);
    	return result;
    }
    
    private String findDuplicateSubtrees(TreeNode node, Map<String, Integer> cache, List<TreeNode> result) {
    	if(node == null) return "";
    	
    	String left = findDuplicateSubtrees(node.left, cache, result);
    	String right = findDuplicateSubtrees(node.right, cache, result);
    	String thisNode = String.valueOf(node.val);
    	
    	if(!left.equals("")) {
    		thisNode += ("("+ left +")");
    	}
    	
    	if(!right.equals("")) {
    		if(left.equals(""))
    			thisNode += "()";
    		thisNode += ("("+ right +")");
    	}
    	
    	int count = cache.getOrDefault(thisNode, 0);
    	if(count == 1) 
    		result.add(node);
    	cache.put(thisNode, count + 1);
    	
    	return thisNode;
    }
}
